#include "ai.h"
#include "qvector.h"
#define MAX 99999
#define MIN -99999

QVector<GameState>childStateList;

int max(int a,int b){
	if(a>b)return a;
	else return b;
}
int min(int a,int b){
	if(a<b)return a;
		else return b;
}

int maxDepth = 0;
int nodeNum = 0;
int maxPruning = 0;
int minPruning = 0;

int ddx[3] = {-1,0,1};
int ddy[3] = {-1,0,1};

ai::ai(QWidget *parent)
    : QWidget(parent)
{
	ui.setupUi(this);
}
/**
 * Init Process
 *
 * **/
void ai::initUiElement(QApplication &AiApp){
	QObject::connect(ui.btnQuit,SIGNAL(clicked()),&AiApp,SLOT(quit()));
	dlgSet = new SetDialog(0);
	QObject::connect(ui.btnSet,SIGNAL(clicked()),dlgSet,SLOT(open()));
	QObject::connect(dlgSet->btnApply,SIGNAL(clicked()),this,SLOT(changeSetting()));
}
/**
 * Init GameBoard by a gamestate
 * @access private
 * **/
void ai::renderGameBoard(const GameState &state){
	int n = state.boardSize;
	gridTable = new Grid*[n];
	for(int i=0;i<n;i++){
		gridTable[i] = new Grid[n];
	    for(int j=0;j<n;j++){
			gridTable[i][j].x = i;
			gridTable[i][j].y = j;
			gridTable[i][j].setWidget(this);
	    	gridTable[i][j].setParent(this);
	     	gridTable[i][j].setObjectName(QString::fromUtf8("grid"+i+j));
	    	gridTable[i][j].setGeometry(QRect(160+i*30, 20+j*30, 30, 30));
	    	gridTable[i][j].setValue(currentState.ptrState[i][j]);
	    	gridTable[i][j].show();
	    }
	  }
 	this->setWindowTitle(QApplication::translate("aiClass", "Game Start", 0, QApplication::UnicodeUTF8));
	this->update();
}

/**
 * changeSetting of a game and start a new game
 * @access private
 **/
void ai::changeSetting(){
	setting = dlgSet->getSetting();
	dlgSet->close();
	currentState = generateGameState(setting);
	renderGameBoard(currentState);
	currentState.depth = 0;
	changeBoard(currentState);
}
/**
 * generate a board of othello from GameSetting
 * @param gameSetting
 * @return gameState
 */
GameState ai::generateGameState(const GameSetting &setting){
	GameState state(setting);
	return state;
}

/**
 * take the action and change the currentstate
 */
void ai::moveNextStep( int i, int j){
	//if the move is valid or there is no valid move exists
	if(currentState.isValidNextStep(i,j)||(i==-1&&j==-1)){
		currentState = getNextState(i,j,currentState);
		changeBoard(currentState);
 	}
}

/**
 * change of board from a given state;
 * @param currentState
 */
void ai::changeBoard(GameState& currentState){

	int n = currentState.boardSize;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			gridTable[i][j].setValue(currentState.ptrState[i][j]);
			gridTable[i][j].show();
		}
	}
	QString endState;
	//swith to AI
	if(currentState.turnNumber == 1){
		if(currentState.testTerminate() ==false){
		Action nextAction = this->Alpha_Beta_Search(currentState);
		moveNextStep(nextAction.x,nextAction.y);
		}
	}
	flushText(currentState);
	this->update();
	//if not terminate and no valid move for one side,
	//just swap the turn(by taking action(-1-1))
	if(currentState.testTerminate() ==false){
		if(currentState.existValidMove() == false){
			moveNextStep(-1,-1);
		}
		flushText(currentState);
	}

}
/**
 * generate a state with :perform effect of "Eating"(reverse the x and o),and reverse turnNumber
 * @param i
 * @param j
 * @param state
 * @return GameState newState;
 */
GameState ai::getNextState(const int& i,const int& j,const GameState& state){
	int boardSize= state.boardSize;
	GameState newState(state);
	//if there is valid move
	if(!(i==-1&&j==-1)){
		for(int m=0;m<=2;m++){
			for(int n=0;n<=2;n++){
				if(i+ddx[m]>=boardSize||i+ddx[m]<0||j+ddy[n]>=boardSize||j+ddy[n]<0)
					continue;
				if(state.ptrState[i+ddx[m]][j+ddy[n]] == -state.turnNumber){
					for(int xx=i+ddx[m],yy=j+ddy[n];xx>=0 && xx< boardSize &&yy>=0 && yy<boardSize;xx+=ddx[m],yy+=ddy[n]){
						if(state.ptrState[xx][yy] == state.turnNumber){
							int ix = i;int iy = j;
							while(!(ix == xx && iy == yy)){
								newState.ptrState[ix][iy] = state.turnNumber;
								ix+=ddx[m];iy+=ddy[n];
							}
						}
					}
				}
			}
		}
	}
	//when no valid move next, just swap the turn
	newState.depth = state.depth+1;
	maxDepth = max(newState.depth,maxDepth);
	newState.turnNumber = -state.turnNumber;
	return newState;
}

/**
 *  choose a action from algorithm
 * @param GamsState cState, the currentSTATE
 * @return  action which resulted from alpha_beta_search
 */
Action ai::Alpha_Beta_Search(GameState& cState){
	cState.depth = 0;
	maxDepth  = 0;
	nodeNum = 1;
	minPruning = 0;
	maxPruning = 0;
	childStateList.clear();

	int v = Max_Value(cState,MIN,MAX);
	/*look for the action reuslt to the states which has utility = v*/
	cState.getActionList();
	for(int i=0;i<cState.actionList.size();i++){
		GameState nState = getNextState(cState.actionList[i].x,cState.actionList[i].y,cState);
		if(nState.testTerminate()==true){
			return cState.actionList[i];
		}
		for(int soni = 0;soni<childStateList.size();soni++){
			if(nState.equal(childStateList[soni])){
				if(v == childStateList[soni].utility){
					return cState.actionList[i];
				}
			}
		}
	}
}

int ai::Max_Value(GameState& state,int alpha,int beta){
	nodeNum++;

	if(state.testTerminate() == true){
		if(state.depth == 1){
			state.utility = state.getStateValue();
			childStateList.append(state);
			return state.utility;
		}
		return state.getStateValue();
	}
	if(state.cutOff() == true){
		return state.getStateValue();
	}
	//this vector is to record the visited state within this Max_Value()
	QVector<GameState>iteratedList;
	int v = MIN;
	//get all the possible actions ,push in to vector inside state
	state.getActionList();

	for(int i=0;i<state.actionList.size();i++){
		//generate the valid nextstate by applying an action
		GameState nState = getNextState(state.actionList[i].x,state.actionList[i].y,state);
		bool likelyStateVisited = false;

		//search the visited state if a symmetric gamestate exist, if yes, prune this one
		for(int j=0;j<iteratedList.size();j++){
			 if(nState.isLikely(iteratedList[j]) == true){
				likelyStateVisited = true;
				break;
		 	}
		}
	 	if(likelyStateVisited == false){
			v = max(v,Min_Value(nState,alpha,beta));
			iteratedList.append(nState);

		}
		if(v>=beta){
			maxPruning+=(state.actionList.size() - i-1);
			if(state.depth ==1){
				state.utility = v;
				childStateList.append(state);
			}
			return v;
		}
		alpha = max(alpha,v);
	}
	if(state.depth ==1){
		state.utility = v;
		childStateList.append(state);
	}
	return v;
}

int ai::Min_Value(GameState& state,int alpha,int beta){
	nodeNum++;
	if(state.testTerminate() == true){
		if(state.depth == 1){
			state.utility = state.getStateValue();
			childStateList.append(state);
			return state.utility;
		}
		return state.getStateValue();
	}
	if(state.cutOff() == true){
		return state.getStateValue();
	}
	state.getActionList();
	QVector<GameState>iteratedList;
	int v = MAX;

	for(int i=0;i<state.actionList.size();i++){
		GameState nState = getNextState(state.actionList[i].x,state.actionList[i].y,state);
		bool likelyStateVisited = false;
		for(int j=0;j<iteratedList.size();j++){
			if(nState.isLikely(iteratedList[j]) == true){
				likelyStateVisited = true;
				break;
			}
		}
		if(likelyStateVisited == false){
			v = min(v,Max_Value(nState,alpha,beta));
			iteratedList.append(nState);
		}
		if(v<=alpha){
			minPruning+=(state.actionList.size() - i-1);
			if(state.depth ==1){
				state.utility = v;
				childStateList.append(state);
			}
			return v;
		}
		beta = min(beta,v);
	}
	if(state.depth ==1){
		state.utility = v;
		childStateList.append(state);
	}
	return v;
}
/**
 * print the statistic
 */
void ai::flushText(GameState& currentState ){
	QString depth;
	depth.setNum(maxDepth,10);
	ui.depthLabel->setText(QString("MaxDepth:")+depth);
	QString nodeText;
	nodeText.setNum(nodeNum,10);
	ui.nodeLabel->setText(QString("Node#:")+nodeText);
	QString maxPruningText;
	maxPruningText.setNum(maxPruning,10);
	ui.maxPruningLabel->setText(QString("MaxPruning#:")+maxPruningText);
	QString minPruningText;
	minPruningText.setNum(minPruning,10);
	ui.minPruningLabel->setText(QString("MinPruning#:")+minPruningText);

	if(currentState.testTerminate() ==false){
		ui.stateLabel->setText(QString("Game Start"));
		ui.resultLabel->setText(QString(" "));
	}else{
		ui.stateLabel->setText(QString("Game End"));
		if(currentState.getStateValue()>0){
			ui.resultLabel->setText(QString("AI Win!"));
		}
		if(currentState.getStateValue()==0){
			ui.resultLabel->setText(QString("Draw!"));
		}
		if(currentState.getStateValue()<0){
			ui.resultLabel->setText(QString("You Win!"));
		}
	}
}
/**
 * destroy
 * @return
 */
ai::~ai(){}
/**
 * whenever a grided is clicked, call the mainclass's function
 */
void Grid::onClicked(){
	mainClass->moveNextStep(x,y);
}
